#define _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_DEPRECATE

/* in code we trust */

/*
	Input: graph G(set V, set E:(+weight)).
	Output: graph Q(set V, set E), sum{E.weight} = min.

	Step 1. 
		Answer is graph Q(V, nil);
	Step 2. 
		Sort edges G.E by non-descreasing;
	Step 3, main iterations.
		Beginning from the edge with minimal weight, add them
		to Q, if they don't create a cycle in Q. Repeat that, 
		while Q.E| < G.V|.
		For preventing of cycle creation, use DCU.
*/

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <deque>
#include <string>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <limits>
 
using namespace std;

#define _ << " "
#define __ << " " <<
#define eol << "\n"
#define eol_ << "\n" <<
#define prec(_value) fixed << setprecision(_value) <<

#define uint unsigned int
#define oint long long
#define lod  long double

#define forx(i,n)   for (int i = 0; i < n; i++)
#define rforx(i, n) for (int i = n; i >= 0; i--)
#define repx(i,n,s) for (int i = 0; i < n; i += s)
#define allx(str) str.begin(), str.end()
#define rallx(str) str.rbegin(), str.rend()
const double eps = 1e-8;

struct edge
{
	int from, to, weight;
};

/* dcu */
class dcu
{
public:
	void init(int);
	int root(int);
	void join(int, int);
private:
	vector <int> anc;
};

void dcu::init(int n)
{
	srand(n);
	anc.resize(n);
	forx(i, n)
		anc[i] = i;
}

int dcu::root(int v)
{
	return (v == anc[v]) ? v : anc[v] = root(anc[v]);
}

void dcu::join(int a, int b)
{
	a = root(a);
	b = root(b);
	if (a == b)
		return;
	if (rand() & 1)
		swap(a, b);
	anc[a] = b;
}

/* dcu ends */

pair <oint, vector <edge> > min_carcass(vector <edge> &g, int n)
	// cruscal algo
{
	// Step 2: sorting edges by non-descreasing
	sort(allx(g), [] (edge e1, edge e2)
		{
			return e1.weight < e2.weight;
		});

	dcu s;
	s.init(n);
	oint answer = 0;
	vector <edge> answer_e;

	forx(i, g.size())
	{
		/* if roots are equal, then there vertexes are already in Q,
		so we shouldn't add this edge to Q */
		if (s.root(g[i].from) == s.root(g[i].to))
			continue;
		else
			s.join(g[i].from, g[i].to),
			answer += g[i].weight,
			answer_e.push_back(g[i]);
		if (answer_e.size() == n - 1)
			break;
	}

	return make_pair(answer, answer_e);
}

/*
int main()
{
#ifdef CUCUMBER
	freopen("input.txt","r",stdin);
	freopen("output.txt","w+",stdout);
#endif

	int n, m;
	cin >> n >> m;
	vector <edge> g(m);
	forx(i, m)
	{
		cin >> g[i].from >> g[i].to >> g[i].weight;
		g[i].from--; g[i].to--;
	}

	pair <oint, vector <edge> > answer = min_carcass(g, n);

	cout << answer.first eol;
	return 0;
} 
*/
